package m202405.d14;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: 爱做梦的锤子
 * @date: 2024/5/14 08:38
 */
public class Q208 {
    public static class Trie {

        Map<Character, Node> head;

        public Trie() {
            head = new HashMap<>();
        }

        public void insert(String word) {
            Map<Character, Node> temp = head;
            Node last = null;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                Node node = temp.get(c);
                if (node == null) {
                    node = new Node(c);
                    temp.put(c, node);
                }
                last = node;
                temp = node.next;
            }
            if (last != null) {
                last.isEnd = true;
            }
        }

        public boolean search(String word) {
            Map<Character, Node> temp = head;
            Node last = null;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                Node node = temp.get(c);
                if (node == null) {
                    return false;
                }
                temp = node.next;
                last = node;
            }
            if (temp.isEmpty()) {
                return true;
            }
            return last == null ? false : last.isEnd;
        }

        public boolean startsWith(String prefix) {
            Map<Character, Node> temp = head;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                Node node = temp.get(c);
                if (node == null) {
                    return false;
                }
                temp = node.next;
            }
            return true;
        }

        public static class Node {
            char val;
            boolean isEnd;
            Map<Character, Node> next;

            public Node(char val) {
                this.val = val;
                this.isEnd = false;
                this.next = new HashMap<>();
            }
        }
    }
}
